public class CC36 {
    //给定两个字符串S和T，返回S子序列等于T的不同子序列个数有多少个？
    //字符串的子序列是由原来的字符串删除一些字符（也可以不删除）在不改变相对位置的情况下的剩余字符（例如，"ACE"is a subsequence of"ABCDE"但是"AEC"不是）
    //例如：
    //S="nowcccoder", T = "nowccoder"
    //返回3
    public int numDistinct (String S, String T) {
        int row = S.length();
        int col = T.length();
        int[][] numD = new int[row + 1][col + 1];
        numD[0][0] = 1;
        for (int i = 1; i <= row; i++) {
            numD[i][0] = 1;
        }
        for (int i = 1; i <= col; i++) {
            numD[0][i] = 0;
        }
        for (int i = 1; i <= row; i++) {
            for (int j = 1; j <= col; j++) {
                if(S.charAt(i - 1) == T.charAt(j - 1)) {
                    numD[i][j] = numD[i - 1][j - 1] + numD[i - 1][j];
                }else {
                    numD[i][j] = numD[i - 1][j];
                }
            }
        }
        return  numD[row][col];
    }
}
